import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;

public class QuickFindUF {
  private int[] id; // 分量ID
  private int count; // 分量数量

  public QuickFindUF(int N) {
    count = N;// 初始化分量数量和id数组
    id = new int[N];
    for (int i = 0; i < N; i++) {
      id[i] = i; // 设置每个数组的值为自己的索引
    }
  }

  public int count() {
    return count; // 返回分量数量
  }

  public boolean connected(int p, int q) {
    return find(p) == find(q); // 判断两个下标对应的值是否相等
  }

  public int find(int p) {
    return id[p]; // 返回下标对应的值
  }

  public void union(int p, int q) { // 将q和q归并到相同的分量中
    int pID = find(p);
    int qID = find(q);

    if (pID == qID)
      return; // 如果两个下标值相同则表明在相同的分量中
    for (int i = 0; i < id.length; i++) { // 这里效率会很慢
      if (id[i] == pID) {
        id[i] = qID; // 将数组中值等于pID的改为qID
      }
    }
    count--;
  }

  public static void main(String[] args) {
    int N = StdIn.readInt();
    StdOut.println("N === " + N);
    QuickFindUF uf = new QuickFindUF(N);
    while (!StdIn.isEmpty()) {
      int p = StdIn.readInt();
      int q = StdIn.readInt();
      if (uf.connected(p, q)) {
        continue;
      }
      uf.union(p, q);
      StdOut.println(p + " " + q);
    }
    StdOut.println(uf.count() + "components");
  }
}
